//买卖股票多次操作
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int days = prices.size();
        vector<vector<int>> dp(days,vector<int>(k*2+1));
        for(int i=1; i<=k; i++){
            dp[0][i*2-1] = -prices[0]; 
            dp[0][i*2] = 0;    
        }

        for(int i=1; i<days; i++){
            for(int j=1; j<=k; j++){
                dp[i][j*2-1] = max(dp[i-1][(j-1)*2]-prices[i],dp[i-1][j*2-1]); 
                dp[i][j*2] = max(dp[i-1][j*2-1]+prices[i],dp[i-1][j*2]);    
            }
        }
        return dp[days-1][2*k];
    }
};